/*
** 3368.c
** 
** Made by (frank)
** Login   <frank@FrankChen>
** 
** Started on  Tue Sep 30 14:55:23 2008 frank
** Last update Sun May 12 01:17:25 2002 Speed Blue
*/

/*
 * EXPERIENCE: sometimes ds is neccesary....
 */

/* #include "3368.h" */
#include <stdio.h>

typedef struct _info
{
     int previous;
     int next;
     int count;
} info;
     
int main()
{
     int n, q;
     info num[200001];
     int i, prev, tmp, conv, first, last;
     int l, r;

     int cur, cur_n, max;

     /* INITIALIZE */
     for(i = 0; i < 200001; i++)
	  num[i].count = 0;

     scanf("%d %d", &n, &q);
     /* FIRST number */
     scanf("%d", &tmp);
     conv = tmp + 100000;
     num[conv].count++;
     num[conv].previous = conv;
     prev = tmp;
     first = conv;
     /* STORE the info of each num */
     i = 1;
     while(i < n){
	  scanf("%d", &tmp);
	  if (prev == tmp)
	       num[conv].count++;
	  else{
	       conv = tmp + 100000;
	       prev += 100000;
	       num[prev].next = conv;
	       num[conv].previous = prev;
	       num[conv].count++;
	       prev = tmp;
	  }
	  i++;
     }
     last = conv;
     num[last].next = last;
     /* DEAL with the queries */
     while(q){
	  scanf("%d%d", &l, &r);
	  if (l == r){
	       printf("1\n");
	       continue;
	  }
	  if (l > n - r){	/* should start from last */
	       cur = last;
	       cur_n = n;
	       while(cur_n >= r){
		    cur_n -= num[cur].count;
		    cur = num[cur].previous;
	       }
	       max = r - cur_n;	/* (part of)the current num counts */
	       while(cur_n >= l){
		    if (cur_n - l <= num[cur].count)
			 break;
		    if (num[cur].count > max)
			 max = num[cur].count;
		    cur_n -= num[cur].count;
		    cur = num[cur].previous;
	       }
	       if (cur_n - l > max)
		    max = cur_n - l;
	       printf("%d\n", max);
	  }
	  else{			/* should start from first */
	       cur = first;
	       cur_n = 1;
	       while(cur_n <= l){
		    cur_n += num[cur].count;
		    cur = num[cur].next;
	       }
	       max = cur_n - l;
	       while(cur_n <= r){
		    if (r - cur_n <= num[cur].count)
			 break;
		    if (num[cur].count > max)
			 max = num[cur].count;
		    cur_n += num[cur].count;
		    cur = num[cur].next;
	       }
	       if (r - cur_n > max)
		    max = r - cur_n;
	       printf("%d\n", max);
	  }
	  q--;
     }
     scanf("%d", &tmp);
     
     return 0;
}

		    
	       
	  
